home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 8: LINUX Games / Linux Cubed Series 8 - LINUX Games.iso / games / x11 / rpg / crossfir.92 / crossfir / crossfire-0.92.5 / common / shstr.c < prev    next >
C/C++ Source or Header  |  1996-07-24  |  9KB  |  392 lines
  1. /*
  2.  * static char *rcsid_shstr_c =
  3.  *   "$Id: shstr.c,v 1.16 1994/04/16 00:24:28 master Exp $";
  4.  *
  5.  * shstr.c
  6.  *
  7.  * This is a simple shared strings package with a simple interface.
  8.  *
  9.  *     char *find_string(const char *str)
  10.  *     char *add_string(const char *str)
  11.  *    char *add_refcount(char *str)
  12.  *    void free_string(char *str)
  13.  *    char *ss_dump_table(int what)
  14.  *    void ss_dump_statistics()
  15.  *
  16.  * Author: Kjetil T. Homme, Oslo 1992.
  17.  */
  18.  
  19. #include <stdio.h>
  20. #include <stddef.h>
  21. #include <stdlib.h>
  22. #include <sys/types.h>
  23. #include <limits.h>
  24. #include <string.h>
  25.  
  26. #if defined (__sun__) && defined (StupidSunHeaders)
  27. #include <sys/time.h>
  28. #include "sunos.h"
  29. #endif
  30.  
  31. #include "shstr.h"
  32.  
  33. static shared_string *hash_table[TABLESIZE];
  34.  
  35. /*
  36.  * Initialises the hash-table used by the shared string library.
  37.  */
  38.  
  39. void
  40. init_hash_table() {
  41.     /* A static object should be zeroed out always */
  42. #if !defined(__STDC__)
  43.     (void) memset((void *)hash_table, 0, TABLESIZE * sizeof(shared_string *));
  44. #endif
  45. }
  46.  
  47. /*
  48.  * Hashing-function used by the shared string library.
  49.  */
  50.  
  51. static int
  52. hashstr(const char *str) {
  53.     unsigned long hash = 0;
  54.     int i = 0, rot = 0;
  55.     const char *p;
  56.  
  57.     GATHER(hash_stats.calls);
  58.  
  59.     for (p = str; i < MAXSTRING && *p; p++, i++) {
  60.     hash ^= (unsigned long) *p << rot;
  61.     rot += 2;
  62.     if (rot >= (sizeof(long) - sizeof(char)) * CHAR_BIT)
  63.         rot = 0;
  64.     }
  65.     return (hash % TABLESIZE);
  66. }
  67.  
  68. /*
  69.  * Allocates and initialises a new shared_string structure, containing
  70.  * the string str.
  71.  */
  72.  
  73. static shared_string *
  74. new_shared_string(const char *str) {
  75.     shared_string *ss;
  76.  
  77.     /* Allocate room for a struct which can hold str. Note
  78.      * that some bytes for the string are already allocated in the 
  79.      * shared_string struct.
  80.      */
  81.     ss = (shared_string *) malloc(sizeof(shared_string) - PADDING +
  82.                   strlen(str) + 1);
  83.     ss->u.previous = NULL;
  84.     ss->next = NULL;
  85.     ss->refcount = 1;
  86.     strcpy(ss->string, str);
  87.  
  88.     return ss;
  89. }
  90.  
  91. /*
  92.  * Description:
  93.  *      This will add 'str' to the hash table. If there's no entry for this
  94.  *      string, a copy will be allocated, and a pointer to that is returned.
  95.  * Return values:
  96.  *      - pointer to string identical to str
  97.  */
  98.  
  99. char *
  100. add_string(const char *str) {
  101.     shared_string *ss;
  102.     int ind;
  103.  
  104.     GATHER(add_stats.calls);
  105.  
  106.     /* Should really core dump here, since functions should not be calling
  107.      * add_string with a null parameter.  But this will prevent a few
  108.      * core dumps.
  109.      */
  110.     if (str==NULL) {
  111. #ifdef MANY_CORES
  112.     abort();
  113. #else
  114.     return NULL;
  115. #endif
  116.     }
  117.  
  118.     ind = hashstr(str);
  119.     ss = hash_table[ind];
  120.  
  121.     /* Is there an entry for that hash?
  122.      */
  123.     if (ss) {
  124.     /* Simple case first: See if the first pointer matches.
  125.      */
  126.     if (str != ss->string) {
  127.         GATHER(add_stats.strcmps);
  128.         if (strcmp(ss->string, str)) {
  129.         /* Apparantly, a string with the same hash value has this 
  130.          * slot. We must see in the list if "str" has been 
  131.          * registered earlier.
  132.          */
  133.         while (ss->next) {
  134.             GATHER(add_stats.search);
  135.             ss = ss->next;
  136.             if (ss->string != str) {
  137.             GATHER(add_stats.strcmps);
  138.             if (strcmp(ss->string, str)) {
  139.                 /* This wasn't the right string...
  140.                  */
  141.                 continue;
  142.             }
  143.             }
  144.             /* We found an entry for this string. Fix the
  145.              * refcount and exit.
  146.              */
  147.             GATHER(add_stats.linked);
  148.             ++(ss->refcount);
  149.  
  150.             return ss->string;
  151.         }
  152.         /* There are no occurences of this string in the hash table.
  153.          */
  154.         {
  155.             shared_string *new_ss;
  156.  
  157.             GATHER(add_stats.linked);
  158.             new_ss = new_shared_string(str);
  159.             ss->next = new_ss;
  160.             new_ss->u.previous = ss;
  161.             return new_ss->string;
  162.         }
  163.         }
  164.         /* Fall through.
  165.          */
  166.     }
  167.     GATHER(add_stats.hashed);
  168.     ++(ss->refcount);
  169.     return ss->string;
  170.     } else {
  171.     /* The string isn't registered, and the slot is empty.
  172.      */
  173.     GATHER(add_stats.hashed);
  174.     hash_table[ind] = new_shared_string(str);
  175.  
  176.     /* One bit in refcount is used to keep track of the union.
  177.      */
  178.     hash_table[ind]->refcount |= TOPBIT;
  179.     hash_table[ind]->u.array = &(hash_table[ind]);
  180.  
  181.     return hash_table[ind]->string;
  182.     }
  183. }
  184.  
  185. /*
  186.  * Description:
  187.  *      This will increase the refcount of the string str, which *must*
  188.  *      have been returned from a previous add_string().
  189.  * Return values:
  190.  *      - str
  191.  */
  192.  
  193. char *
  194. add_refcount(char *str) {
  195.     GATHER(add_ref_stats.calls);
  196.     ++(SS(str)->refcount);
  197.     /* This function should be declared 
  198.      *    const char *add_refcount(const char *)
  199.      * Unfortunately, that would require changing a lot of structs
  200.      */
  201.     return str;
  202. }
  203.  
  204. /*
  205.  * Description:
  206.  *      This will return the refcount of the string str, which *must*
  207.  *      have been returned from a previous add_string().
  208.  * Return values:
  209.  *      - length
  210.  */
  211.  
  212. int
  213. query_refcount(const char *str) {
  214.     return SS(str)->refcount;
  215. }
  216.  
  217. /*
  218.  * Description:
  219.  *      This will see if str is in the hash table, and return the address
  220.  *      of that string if it exists.
  221.  * Return values:
  222.  *      - pointer to identical string or NULL
  223.  */
  224.  
  225. char *
  226. find_string(const char *str) {
  227.     shared_string *ss;
  228.     int ind;
  229.  
  230.     GATHER(find_stats.calls);
  231.  
  232.     ind = hashstr(str);
  233.     ss = hash_table[ind];
  234.  
  235.     /* Is there an entry for that hash?
  236.      */
  237.     if (ss) {
  238.     /* Simple case first: Is the first string the right one?
  239.      */
  240.     GATHER(find_stats.strcmps);
  241.     if (!strcmp(ss->string, str)) {
  242.         GATHER(find_stats.hashed);
  243.         return ss->string;
  244.     } else {
  245.         /* Recurse through the linked list, if there's one.
  246.          */
  247.         while (ss->next) {
  248.         GATHER(find_stats.search);
  249.         GATHER(find_stats.strcmps);
  250.         ss = ss->next;
  251.         if (!strcmp(ss->string, str)) {
  252.             GATHER(find_stats.linked);
  253.             return ss->string;
  254.         }
  255.         }
  256.         /* No match. Fall through.
  257.          */
  258.     }
  259.     }
  260.     return NULL;
  261. }
  262.  
  263. /*
  264.  * Description:
  265.  *     This will reduce the refcount, and if it has reached 0, str will
  266.  *     be freed.
  267.  * Return values:
  268.  *     None
  269.  */
  270.  
  271. void
  272. free_string(char *str) {
  273.     shared_string *ss;
  274.  
  275.     GATHER(free_stats.calls);
  276.  
  277.     ss = SS(str);
  278.  
  279.     if ((--ss->refcount & ~TOPBIT) == 0) {
  280.     /* Remove this entry.
  281.      */
  282.     if (ss->refcount & TOPBIT) {
  283.         /* We must put a new value into the hash_table[].
  284.          */
  285.         if (ss->next) {
  286.         *(ss->u.array) = ss->next;
  287.         ss->next->u.array = ss->u.array;
  288.         ss->next->refcount |= TOPBIT;
  289.         } else {
  290.         *(ss->u.array) = NULL;
  291.         }
  292.         free(ss);
  293.     } else {
  294.         /* Relink and free this struct.
  295.          */
  296.         if (ss->next)
  297.         ss->next->u.previous = ss->u.previous;
  298.         ss->u.previous->next = ss->next;
  299.         free(ss);
  300.     }
  301.     }
  302. }
  303.  
  304. #ifdef SS_STATISTICS
  305.  
  306. extern char errmsg[];
  307.  
  308. /*
  309.  * Description:
  310.  *      The routines will gather statistics if SS_STATISTICS is defined.
  311.  *      A call to this function will cause the statistics to be dumped
  312.  *      into an external string errmsg, which must be large.
  313.  * Return values:
  314.  *      None
  315.  */
  316.  
  317. void
  318. ss_dump_statistics() {
  319.     static char line[80];
  320.  
  321.     sprintf(errmsg, "%-13s %6s %6s %6s %6s %6s\n", 
  322.         "", "calls", "hashed", "strcmp", "search", "linked");
  323.     sprintf(line, "%-13s %6d %6d %6d %6d %6d\n", 
  324.         "add_string:", add_stats.calls, add_stats.hashed, 
  325.         add_stats.strcmps, add_stats.search, add_stats.linked);
  326.     strcat(errmsg, line);
  327.     sprintf(line, "%-13s %6d\n",
  328.         "add_refcount:", add_ref_stats.calls);
  329.     strcat(errmsg, line);
  330.     sprintf(line, "%-13s %6d\n",
  331.         "free_string:", free_stats.calls);
  332.     strcat(errmsg, line);
  333.     sprintf(line, "%-13s %6d %6d %6d %6d %6d\n", 
  334.         "find_string:", find_stats.calls, find_stats.hashed, 
  335.         find_stats.strcmps, find_stats.search, find_stats.linked);
  336.     strcat(errmsg, line);
  337.     sprintf(line, "%-13s %6d\n",
  338.         "hashstr:", hash_stats.calls);
  339.     strcat(errmsg, line);
  340. }
  341. #endif /* SS_STATISTICS */
  342.  
  343. /*
  344.  * Description:
  345.  *      If (what & SS_DUMP_TABLE) dump the contents of the hash table to
  346.  *      stderr. If (what & SS_DUMP_TOTALS) return a string which
  347.  *      says how many entries etc. there are in the table.
  348.  * Return values:
  349.  *      - a string or NULL
  350.  */
  351.  
  352. char *
  353. ss_dump_table(int what) {
  354.     static char totals[80];
  355.     int entries = 0, refs = 0, links = 0;
  356.     int i;
  357.  
  358.     for (i = 0; i < TABLESIZE; i++) {
  359.     shared_string *ss;
  360.     
  361.     if ((ss = hash_table[i])!=NULL) {
  362.         ++entries;
  363.         refs += (ss->refcount & ~TOPBIT);
  364. #if 0 /* Can't use stderr any longer, need to include global.h and
  365.         if (what & SS_DUMP_TABLE)
  366.        * use logfile. */
  367.         fprintf(stderr, "%4d -- %4d refs '%s' %c\n",
  368.             i, (ss->refcount & ~TOPBIT), ss->string,
  369.             (ss->refcount & TOPBIT ? ' ' : '#'));
  370. #endif
  371.         while (ss->next) {
  372.         ss = ss->next;
  373.         ++links;
  374.         refs += (ss->refcount & ~TOPBIT);
  375. #if 0
  376.         if (what & SS_DUMP_TABLE)
  377.             fprintf(stderr, "     -- %4d refs '%s' %c\n",
  378.                 (ss->refcount & ~TOPBIT), ss->string,
  379.                 (ss->refcount & TOPBIT ? '*' : ' '));
  380. #endif
  381.         }
  382.     }
  383.     }
  384.  
  385.     if (what & SS_DUMP_TOTALS) {
  386.     sprintf(totals, "\n%d entries, %d refs, %d links.",
  387.         entries, refs, links);
  388.         return totals;
  389.     }
  390.     return NULL;
  391. }
  392.